Arrays

Resource: Neetcode.

I. Static Arrays

1. Introduction

Arrays are a way of storing data contiguously - ”adjacently”.

• In strictly typed languages like Java, C++, C#, etc, arrays have an allocated size when initialized. → static arrays → the size of the array cannot change after initialization.
• Loosely typed languages such as Python and JavaScript do not have static arrays, they use dynamic arrays.

The most commons operations we can perform on an array are: reading, deletion, and insertion.

2. Reading from an Array

Array elements are accessed through indices, which start at index 0. Reading from an array is as simple as accessing the index of the element in that array.

myArray = [1, 3, 4] # array initialization

# access an arbitrary element, where i is the index of the desired value
myArray[i]

As long as the index of an element is known, the access is instant. This is because each value at an index of the array is mapped to an address in RAM.

• Regardless of the size of the input, the time taken to access the element at the given index is always unaffected and instant. → O(1) time complexity.

Traversing through an array

Traversing through an array means that we iterate through all the values of an array, usually we do that using a loop.

for i in range(len(myArray)):
   print(myArray[i])

# OR

i = 0
while i < len(myArray):
   print(myArray[i])
   i += 1

• Traversal through an array of size n is O(n) → the number of operations is linear to n.
• The number of operations grows linearly with the size of the array. In the example above, if the size of n is doubled, the number of operations for traversal would also double.

3. Deleting from an array

1. Deleting from the end of the array

• In strictly typed languages, all array indices are filled with 0s or some default value upon initialization, denoting an empty array.
• When we want to remove an element from the last index of an array, setting its value to 0 / null or -1 does the job.
• We will also reduce the length by 1 since we have one less element in the array after deletion.
• Because we can have instant access to the last element of the array, deleting the last element of the array is always O(1).

def removeEnd(arr, length): 
	if length > 0: 
		arr[length - 1] = 0 #setting the last index's value to 0

2. Deleting at an ith index

When we want to delete an element at a random index i, we won’t be able to perform this in O(1).

• We can’t just replace the value at that index i with a 0, we have to shift each element from i + 1 till the end of the array 1 position to the left, otherwise we’d break the contiguous order of array.
• In the worst case scenario, if we want to delete the first element of the array, we’d need to shift all the elements to the left. → O(n) time complexity A good approach would be:

• The deletion index is i. We iterate starting from i + 1 until the end of the array.
• We shift each element one index position to the left.
• We replace the last element with a 0 or null to mark it empty, and decrement the length by 1. (optional)

# Assuming i is a valid index.

# Remove value at index i before shifting elements to the left.
def removeMiddle(arr, i, length):
    # Shift starting from i + 1 to end to the left
    for index in range(i + 1, length):
        arr[index - 1] = arr[index]
    
    # No need to 'remove' arr[i], since we already shifted and overwrite it

	# replace the last element with null, decrement length by 1
    arr[length - 1] = None
    return length - 1

4. Insertion

1. Inserting at the end of the array

Since we can always access the last index of the array, inserting an element at the end of an array is O(1) time.

# Insert n into arr at the next open position.
# Length is the number of 'real' values in arr, and 
# capacity is the size (aka memory allocated for the fixed size array).
def insertEnd(arr, n, length, capacity):
    if length < capacity:
        arr[length] = n

2. Inserting at the ith index

• If we insert at index i as is, we would overwrite the current value. To insert without overwriting existing values, we need to shift all values from i one position to the right.

# Insert n into index i after shifting elements to the right.
# Assuming i is a valid index and arr is not full.
def insertMiddle(arr, i, n, length):
    # Shift starting from the end to i.
    for index in range(length - 1, i - 1, -1):
        arr[index + 1] = arr[index]
    
    # Insert at i
    arr[i] = n

Summary

1. Complexity Chart

2. Suggested Problems

Problem	Difficulty	Solution	Category
Remove Duplicates from Sorted Array	Easy	Neetcode	Array, Two Pointers
Remove Element	Easy	Neetcode	Array, Two Pointers

II. Dynamic Arrays

Dynamic Arrays are more common and useful thanks to their ability to resize. Dynamic arrays are the default types of array for Python and JavaScript.

• For static arrays, we specify the size of the array when we created that array.
• But for a dynamic array, you don’t necessarily need have to specify the size. If you don’t specify the size, usually it’ll specify the array to a default size.

Operations on Dynamic Arrays

• When we push a value to the dynamic array, we are adding a value to the end of the array, to the next available empty index.
• When we pop a value from the dynamic array, we are removing a value from the end of the array. → Both of these operations have a time complexity of O(1) because we can always access the last value instantly.

Since the array is dynamic, adding another elementwhen we run out of capacity is achieved by copying over the values of the current array to a new array that is the double the original size.

# Insert n in the last position of the array
def pushback(self, n):
    if self.length == self.capacity:
        self.resize()
        
    # insert at next empty position
    self.arr[self.length] = n
    self.length += 1

• Double the size is a middle ground between not having to allocate a brand new array every time we add a new element, and not wanting to having a bunch of empty space.
• When all the elements from the first array have been copied over, the first static array will be deallocated.

→ This operation will run in amortized O(1).

Amortized time complexity is the average time taken per operation over a sequence of operations. The resize operation itself is O(n)O(n), but since it is not performed every time we add an element, the average time taken per operation is O(1)O(1). But this is only the case if we double the size of the array when we run out of space.

Summary

1. Complexity Chart

2. Suggested Problems

Problem	Difficulty	Solution	Category
Concatenation of Array	Easy	Neetcode	Array, Simulation

III. Stacks

Resource

• Stacks Operations

Stacks are a dynamic data structure that operate on a LIFO (Last In First Out) manner. The last element added to the stack is the first element that comes out. The stack supports three operations - push, pop, peek.

1. Push

The push operation adds an element to the top of the stack, like a dynamic array would append an element to the end. This is an efficient O(1) operation.

Since a stack will remove elements in the reverse order that they were inserted in, it can be used to reverse sequences - such as a string, which is just a sequence of characters.

2. Pop

The pop operation removes the last element from top of the stack, like a dynamic array would pop the last element. This operation is also an efficient O(1).

3. Peek

The peek operation is the simplest, it simply returns the top element without removing it. This also has O(1) complexity.

Summary

1. Time Complexity

2. Suggested Problems

Problem	Difficulty	Solution	Category
Valid Parentheses	Easy	Neetcode	Stacks